import java.util.ArrayList;
import java.util.List;
// https://leetcode.cn/problems/permutations/
public class Permute {
    class Solution {

        private List<List<Integer>> res = new ArrayList<>();
        private boolean [] state;
        public List<List<Integer>> permute(int[] nums) {
            state = new boolean[nums.length];

            backTracking(new ArrayList<>() ,nums);


            return res;


        }
        private void backTracking(List<Integer> path, int[] nums)
        {
            if(path.size() == (nums.length))
            {
                res.add(new ArrayList<>(path));
                return;
            }

            for(int i = 0 ; i < nums.length ; i ++)
            {
                if(!state[i])
                {
                    path.add(nums[i]);
                    state[i] = true;
                    backTracking(path,nums);
                    path.remove(path.size()-1);
                    state[i] = false;
                }
            }
        }
    }
}
